package com.ls.day15;

import java.util.*;

/**
 * @author ：xxx
 * @description：TODO
 * @date ：2021/3/31 9:59
 */
public class CombinationSum {
    public List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        getres(candidates,target);
        HashSet<List<Integer>> set = new HashSet<>(res);
        return new ArrayList<>(set);
    }

    public void getres(int[] candidates, int target){
        if (target==0){
            List<Integer> a = new ArrayList<>(temp);
            res.add(a);
        }
        for (int i=0;i<candidates.length;i++){
            if (candidates[i]<=target){
                if (temp.size()>0&&candidates[i]<temp.get(temp.size()-1)) continue;
                temp.add(candidates[i]);
                getres(candidates,target-candidates[i]);
                temp.remove(temp.size()-1);
            }else{
                break;
            }
        }
    }


}
